#include <iostream>
using namespace std;

/**
 * 不用理解函数内部的意思，因为这是三路快速排序算法，没学过很难看懂
 * 并且用了指针的写法就更难看懂了
 * 只需要理解函数指针的传参应用就行
 */

// 只适用于 int 数组及函数指针
void mySort(int* begin, int* end, bool (*comparer)(int, int)) {
  if (begin >= end - 1) return;
  int pivot = *(begin + rand()%(end - begin));
  int* left = begin;
  int* right = end - 1;
  for (int* iter = begin; iter <= right; ++iter) {
    while (iter < right && comparer(pivot, *iter)) swap(*iter, *right--);
    if (comparer(*iter, pivot)) swap(*iter, *left++);
  }
  mySort(begin, left, comparer);
  mySort(right, end, comparer);
}

bool comp(int a, int b) {
  return a > b;
}

int main() {
  int n = 100;
  int arr[n];
  for (int &x: arr) x = rand() % 100;
  mySort(arr, arr + n, comp);
  for (int &x: arr) cout << x << ' ';
  cout << endl;

  // 测试验证，一旦非法顺序，就死循环
  for (int i = 1; i < n; i ++) {
    while (arr[i] > arr[i-1]);
  }
}